package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class P395LongestSubstringWithAtLeastKRepeatingCharacters {
    public static void main(String[] args) {
        Solution solution = new P395LongestSubstringWithAtLeastKRepeatingCharacters().new Solution();
        System.out.println(solution.longestSubstring("bbaaacbd", 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        public int longestSubstring(String s, int k) {
            return dfs(s, 0, s.length() - 1, k);
        }
        public int dfs(String s, int left, int right, int k) {
            if (left > right) {
                return 0;
            }
            int[] cnt = new int[26];
            for (int i = left; i <= right; i++) {
                cnt[s.charAt(i) - 'a']++;
            }

            for(int i = left; i <= right; i++) {
                if (cnt[s.charAt(i) - 'a'] < k) {
                    return Math.max(dfs(s, i + 1, right, k), dfs(s, left, i - 1, k));
                }
            }

            return right - left + 1;
        }

        public boolean valid(String str, int k) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < str.length(); i++) {
                map.compute(str.charAt(i), (character, integer) -> integer == null ? 1 : integer + 1);
            }
            for (Integer value : map.values()) {
                if (value < k) {
                    return false;
                }
            }
            return true;
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}